#include <iostream>
#include <vector>
#include <algorithm>
#include <unordered_map>

using namespace std;

class Solution
{
public:
    int minSwaps(vector<int> &nums)
    {
        vector<pair<int, int>> sumBit(nums.size(), {0, 0});
        unordered_map<int, int> mp;
        for (int i = 0; i < nums.size(); i++)
        {
            int n = nums[i];
            sumBit[i].second = n;
            while (n > 0)
            {
                sumBit[i].first += n % 10;
                n /= 10;
            }
            mp[nums[i]] = i;
        }
        sort(sumBit.begin(), sumBit.end(), [](pair<int, int> &a, pair<int, int> &b)
             {
            if(a.first == b.first)
                return a.second < b.second;
            else
                return a.first < b.first; });
        int swapCount = 0;
        for (int i = 0; i < sumBit.size(); i++)
        {
            if (sumBit[i].second == nums[i])
                continue;
            int cur = i;
            int nextIndex = mp[sumBit[cur].second];
            while (nextIndex != i)
            {
                swap(nums[cur], nums[nextIndex]);
                cur = nextIndex;
                nextIndex = mp[sumBit[nextIndex].second];
                swapCount++;
            }
        }
        return swapCount;
    }
};
int main()
{
    cout << "Code3551" << endl;
    Solution s;
    vector<int> nums = {268835996, 65052660, 415128775};
    cout << s.minSwaps(nums) << endl;
    return 0;
}